Community Detection and Mining in Social Media





Researching on Simulation of Traffic Accidents Scene by OpenGL.

Fuzzy Expert System Based Intelligent Website Assessment System.

Research on a Multi%2DAgent Based Marketing Cooperation System.

Simulation of Blood Vessels for Surgery Simulators.

Client%2Dside load balancer using cloud.

A Social Network Analysis Approach to Detecting Suspicious Online Financial Activities.

Convergence of Influential Bloggers for Topic Discovery in the Blogosphere.

Sentiment Propagation in Social Networks A Case Study in LiveJournal.

An Integrative Approach to Indentifying Biologically Relevant Genes.

Remote network labs an on%2Ddemand network cloud for configuration testing.

Toward Predicting Collective Behavior via Social Dimension Extraction.

Guest Editors%27 Introduction Social Computing in the Blogosphere.

WisColl Collective wisdom based blog clustering.

Modeling and Data Mining in Blogosphere

Scalable learning of collective behavior based on sparse social dimensions.
The study of collective behavior is to understand how individuals behave in a social network environment. Oceans of data generated by social media like Facebook, Twitter, Flickr and YouTube present opportunities and challenges to studying collective behavior in a large scale. In this work, we aim to learn to predict collective behavior in social media. In particular, given information about some individuals, how can we infer the behavior of unobserved individuals in the same network? A social-dimension based approach is adopted to address the heterogeneity of connections presented in social media. However, the networks in social media are normally of colossal size, involving hundreds of thousands or even millions of actors. The scale of networks entails scalable learning of models for collective behavior prediction. To address the scalability issue, we propose an edge-centric clustering scheme to extract sparse social dimensions. With sparse social dimensions, the socialdimension based approach can efficiently handle networks of millions of actors while demonstrating comparable prediction performance as other non-scalable methods. Categories andSubjectDescriptors H.2.8 [Database Management]: Database applications—
Computing median values in a cloud environment using GridBatch and MapReduce.

Quantifying Utility and Trustworthiness for Advice Shared on Online Social Media.
Abstract—The growing popularity of social media in recent years has resulted in the creation of an enormous amount of user-developed content. While information is readily available, there is no easy way to find the most useful content or to detect whether it is trustworthy. A casual observer might not be able to differentiate between the useful and the useless or the trustworthy and the untrustworthy. In this work, we wish to study the problem of quantifying the value of such user-shared content. In particular, we are focussed on health content as the negative impacts are higher for this domain. We use advice shared on a health social network, Daily Strength, for this study. We describe and define the notions of trustworthiness and utility for social media content. We identify the necessity and challenges for their assessment, and propose a framework that helps address these challenges by identifying relevant features and providing empirical means to meet the requirements for such an evaluation. We select relevant variables and perform numerous experiments to evaluate our models. The results demonstrate promising performance that could possibly be replicated with other social media applications. I.
Web Server Farm in the Cloud Performance Evaluation and Dynamic Architecture.

Web Server Farm in the Cloud Performance Evaluation and Dynamic Architecture.



Uncoverning Groups via Heterogeneous Interaction Analysis.

Integrating Knowledge in Search of Biologically Relevant Genes.

A Social Identity Approach to Identify Familiar Strangers in a Social Network.
We present a novel problem of searching for ‘familiar strangers ’ in a social network. Familiar strangers are individuals who are not directly connected but exhibit some similarity. The power-law nature of social networks determines that majority of individuals are directly connected with a small number of fellow individuals, and similar individuals can be largely unknown to each other. Moreover, the individuals of a social network have only a local view of the network, which makes the problem of aggregating these familiar strangers a challenge. In this work, we formulate the problem, show why it is significant to address the challenge, and present an approach that innovatively employs the social identities of the individuals with competitive approaches. The blogger and citation network are used to showcase technical details and empirical results with related issues and future work.
BlogTrackers A Tool for Sociologists to Track and Analyze Blogosphere.
We present a tool BlogTrackers, which assists sociologists to track and analyze blogs of particular interests by designing and integrating unique features. We present an overview of BlogTrackers, illustrate its functions of various components of BlogTrackers, and outline future work for expansion in meeting the growing needs of sociologists.
Connecting Corresponding Identities across Communities.
One of the most interesting challenges in the area of social computing and social media analysis is the so-called community analysis. A well known barrier in cross-community (multiple website) analysis is the disconnectedness of these websites. In this paper, our aim is to provide evidence on the existence of a mapping among identities across multiple communities, providing a method for connecting these websites. Our studies have shown that simple, yet effective approaches, which leverage social media’s collective patterns can be utilized to find such a mapping. The employed methods successfully reveal this mapping with 66 % accuracy.
Multiclass Probabilistic Kernel Discriminant Analysis.
Kernel discriminant analysis (KDA) is an effective approach for supervised nonlinear dimensionality reduction. Probabilistic models can be used with KDA to improve its robustness. However, the state of the art of such models could only handle binary class problems, which confines their application in many real world problems. To overcome this limitation, we propose a novel nonparametric probabilistic model based on Gaussian Process for KDA to handle multiclass problems. The model provides a novel Bayesian interpretation for KDA, which allows its parameters to be automatically tuned through the optimization of the marginal loglikelihood of the data. Empirical study demonstrates the efficacy of the proposed model. 1
Building a distributed robot garden.

Evaluating the trustworthiness of Wikipedia articles through quality and credibility.
Wikipedia has become a very popular destination for Web surfers seeking knowledge about a wide variety of subjects. While it contains many helpful articles with accurate information, it also consists of unreliable articles with inaccurate or incomplete information. A casual observer might not be able to differentiate between the good and the bad. In this work, we identify the necessity and challenges for trust assessment in Wikipedia, and propose a framework that can help address these challenges by identifying relevant features and providing empirical means to meet the requirements for such an evaluation. We select relevant variables and perform experiments to evaluate our approach. The results demonstrate promising performance that is better than comparable approaches and could possibly be replicated with other social media applications.
Relational learning via latent social dimensions.
Social media such as blogs, Facebook, Flickr, etc., presents data in a network format rather than classical IID distribution. To address the interdependency among data instances, relational learning has been proposed, and collective inference based on network connectivity is adopted for prediction. However, the connections in social media are often multi-dimensional. An actor can connect to another actor due to different factors, e.g., alumni, colleagues, living in the same city or sharing similar interest, etc. Collective inference normally does not differentiate these connections. In this work, we propose to extract latent social dimensions based on network information first, and then utilize them as features for discriminative learning. These social dimensions describe different affiliations of social actors hidden in the network, and the subsequent discriminative learning can automatically determine which affiliations are better aligned with the class labels. Such a scheme is preferred when multiple diverse relations are associated with the same network. We conduct extensive experiments on social media data (one from a real-world blog site and the other from a popular content sharing site). Our model outperforms representative relational learning methods based on collective inference, especially when few labeled data are available. The sensitivity of this model and its connection to existing methods are also carefully examined.
Remote network labs an on%2Ddemand network cloud for configuration testing.

Manipulating Data and Dimension Reduction Methods Feature Selection.

Trust in Blogosphere.

Cross%2DValidation.
The leave-one-out cross-validation scheme for generalization assessment of neural network models is computationally expensive due to replicated training sessions. Linear unlearning of examples has recently been suggested as an approach to approximative crossvalidation. Here we briefly review the linear unlearning scheme, dubbed LULOO, and we illustrate it on a system identification example. Further, we address the possibility of extracting confidence information (error bars) from the LULOO ensemble. 1 Introduction Consider nonlinear regression in which the output y is regressed nonlinearly on the input vector x, this report concerns a neural network implementation, in which the output is predicted by b y = F (x; w) where  F (\Delta) denotes the nonlinear mapping of the neural net and w is the vector of network parameters. The conditional input-output distribution, i.e., the probability distribution of the output conditioned on a test input, is a basic objective for neural net modeling....
A new chi%2Dsquare approximation to the distribution of non%2Dnegative definite quadratic forms in non%2Dcentral normal variables.

Searching for interacting features in subset selection.

Special issue on the best papers of SDM%2709.

Introduction to special issue on social computing

Introduction to special issue on social computing

Understanding the Effects of Sampling on Healthcare Risk Modeling for the Prediction of Future High%2DCost Patients.

GridBatch Cloud Computing for Large%2DScale Data%2DIntensive Batch Applications.

Healthcare Risk Modeling for Medicaid Patients %2D The Impact of Sampling on the Prediction of High%2DCost Patients.

Clustering Blogs with Collective Wisdom.
Blogosphere is expanding in an unprecedented speed. A better understanding of the blogosphere can greatly facilitate the development of the Social Web to serve the needs of users, service providers and advertisers. One important task in this process is clustering blog sites. Clustering blog sites presents new challenges. We propose to tap into collective wisdom in clustering blog sites, present statistical and visual results, report findings, and suggest future work extending to many real-world applications. 1
Robust integration of multiple information sources by view completion.
There are many applications where multiple data sources, each with its own features, are integrated in order to perform an inference task in an optimal way. Researchers have shown that for many tasks like webpage classification, image classification, and pattern recognition, combining data from multiple information sources yields significantly better results than using a single source. In these tasks each of the multiple data sources can be thought of as providing one view of the underlying object. However in many domains not all of the views are available for the available instances; some of the views would be missing. This problem of missing views affects the performance of the machine learning task. In this paper we provide a method of view completion to heuristically predict the missing views. We show that with view completion we are able to achieve significantly better results. We also show that by considering the information at a higher level in terms of views rather than considering them at a lower level in terms of features we are able to achieve better results. We demonstrate this by comparing our method with existing methods which consider the missing views problem as a missing value problem. 1
Heterogeneous data fusion for alzheimer%27s disease study.

Community evolution in dynamic multi%2Dmode networks.
A multi-mode network typically consists of multiple heterogeneous social actors among which various types of interactions could occur. Identifying communities in a multi-mode network can help understand the structural properties of the network, address the data shortage and unbalanced problems, and assist tasks like targeted marketing and finding influential actors within or between groups. In general, a network and the membership of groups often evolve gradually. In a dynamic multi-mode network, both actor membership and interactions can evolve, which poses a challenging problem of identifying community evolution. In this work, we try to address this issue by employing the temporal information to analyze a multi-mode network. A spectral framework and its scalability issue are carefully studied. Experiments on both synthetic data and real-world large scale networks demonstrate the efficacy of our algorithm and suggest its generality in solving problems with complex relationships.
Identifying biologically relevant genes via multiple heterogeneous data sources.
Selection of genes that are differentially expressed and critical to a particular biological process has been a major challenge in post-array analysis. Recent development in bioinformatics has made various data sources available such as mRNA and miRNA expression profiles, biological pathway and gene annotation, etc. Efficient and effective integration of multiple data sources helps enrich our knowledge about the involved samples and genes for selecting genes bearing significant biological relevance. In this work, we studied a novel problem of multi-source gene selection: given multiple heterogeneous data sources (or data sets), select genes from expression profiles by integrating information from various data sources. We investigated how to effectively employ information contained in multiple data sources to extract an intrinsic global geometric pattern and use it in covariance analysis for gene selection. We designed and conducted experiments to systematically compare the proposed approach with representative methods in terms of statistical and biological significance, and showed the efficacy and potential of the proposed approach with promising findings.
Protecting Privacy in Incremental Maintenance for Distributed Association Rule Mining.

Socialtagger %2D collaborative tagging for blogs in the long tail.
Social bookmarking is the process through which users share tags for online resources like blogs with others. Such collaborative tags provide valuable metadata for retrieval systems. While the successes of collaborative tagging systems have been demonstrated by popular websites like Del.icio.us, these sites cover only a small fraction of the available blogs on the web. The vast majority of the blogs are not available on any collaborative tagging system and are often tagged only by the authors. This lack of coverage of collaborative tags is a considerable roadblock in using the tag metadata in a web scale information retrieval system. To solve this problem we propose and implement a system to automatically recommend collaborative tags for a blog. The automatically generated tags will help to surface the blogs by making them available on social book marking sites and allow them to be easily discovered and potentially further tagged by a wider population.
Identifying the influential bloggers in a community.
Blogging becomes a popular way for a Web user to publish information on the Web. Bloggers write blog posts, share their likes and dislikes, voice their opinions, provide suggestions, report news, and form groups in Blogosphere. Bloggers form their virtual communities of similar interests. Activities happened in Blogosphere affect the external world. One way to understand the development on Blogosphere is to find influential blog sites. There are many non-influential blog sites which form the “the long tail”. Regardless of a blog site being influential or not, there are influential bloggers. Inspired by the high impact of the influentials in a physical community, we study a novel problem of identifying influential bloggers at a blog site. Active bloggers are not necessarily influential. Influential bloggers can impact fellow bloggers in various ways. In this paper, we discuss the challenges of identifying influential bloggers, investigate what constitutes influential bloggers, present a preliminary model attempting to quantify an influential blogger, and pave the way for building a robust model that allows for finding various types of the influentials. To illustrate these issues, we conduct experiments with data from a real-world blog site, evaluate multi-facets of the problem of identifying influential bloggers, and discuss unique challenges. We conclude with interesting findings and future work.
Dimensionality Reduction.
Many areas of science
Completing missing views for multiple sources of web media.

Physical topology design for all%2Doptical networks.
Abstract — There are many advantages of deploying an alloptical network. Unfortunately, there are still few guidelines on how to properly design the physical topology for such a network. We propose an efficient physical topology design algorithm and we use the asymptotic growth rate of the provisioned capacity as a metric to compare various design alternatives. A higher asymptotic growth rate translates directly into higher deployment cost for large networks. Our study shows that taking fiber length into consideration can lead to lower capacity requirement. We also find that a sufficiently large fiber-to-node ratio is necessary in order to minimize the asymptotic growth in the provisioned capacity, increase capacity utilization and minimize the need for wavelength conversion. We study a real network and find that its fiber-to-node ratio is too low. As a result, large provisioned capacity is required and less than 55 % of the capacity is usable. By increasing the ratio, we can reduce the provisioned capacity and achieve close to 80 % utilization. I.
Blogosphere research issues%2C tools%2C and applications.
Weblogs, or Blogs, have facilitated people to express their thoughts, voice their opinions, and share their experiences and ideas. Individuals experience a sense of community, a feeling of belonging, a bonding that members matter to one another and their niche needs will be met through online interactions. Its open standards and low barrier to publication have transformed information consumers to producers. This has created a plethora of open-source intelligence, or “collective wisdom ” that acts as the storehouse of overwhelming amounts of knowledge about the members, their environment and the symbiosis between them. Nonetheless, vast amounts of this knowledge still remain to be discovered and exploited in its suitable way. In this paper, we introduce various state-of-the-art research issues, review some key elements of research such as tools and methodologies in Blogosphere, and present a case study of identifying the influential bloggers in a community to exemplify the integration of some major aspects discussed in this paper. Towards the end, we also compare and contrast the blogosphere and social networks and the research therein. 1. INTRODUCTION TO
Topic taxonomy adaptation for group profiling.

Predicting Future High%2DCost Patients A Real%2DWorld Risk Modeling Application.

Adaptive Distance Metric Learning for Clustering.
A good distance metric is crucial for many data mining tasks. To learn a metric in the unsupervised setting, most metric learning algorithms project observed data to a lowdimensional manifold, where geometric relationships such as pairwise distances are preserved. It can be extended to the nonlinear case by applying the kernel trick, which embeds the data into a feature space by specifying the kernel function that computes the dot products between data points in the feature space. In this paper, we propose a novel unsupervised Nonlinear Adaptive Metric Learning algorithm, called NAML, which performs clustering and distance metric learning simultaneously. NAML first maps the data to a high-dimensional space through a kernel function; then applies a linear projection to find a low-dimensional manifold where the separability of the data is maximized; and finally performs clustering in the low-dimensional space. The performance of NAML depends on the selection of the kernel function and the projection. We show that the joint kernel learning, dimensionality reduction, and clustering can be formulated as a trace maximization problem, which can be solved via an iterative procedure in the EM framework. Experimental results demonstrated the efficacy of the proposed algorithm.
Spectral feature selection for supervised and unsupervised learning.
Feature selection aims to reduce dimensionality for building comprehensible learning models with good generalization performance. Feature selection algorithms are largely studied separately according to the type of learning: supervised or unsupervised. This work exploits intrinsic properties underlying supervised and unsupervised feature selection algorithms, and proposes a unified framework for feature selection based on spectral graph theory. The proposed framework is able to generate families of algorithms for both supervised and unsupervised feature selection. And we show that existing powerful algorithms such as ReliefF (supervised) and Laplacian Score (unsupervised) are special cases of the proposed framework. To the best of our knowledge, this work is the first attempt to unify supervised and unsupervised feature selection, and enable their joint study under a general framework. Experiments demonstrated the efficacy of the novel algorithms derived from the framework. 1.
Searching for Interacting Features.
We present a novel Web search interaction feature which, for a given query, provides links to websites frequently visited by other users with similar information needs. These popular destinations complement traditional search results, allowing direct navigation to authoritative resources for the query topic. Destinations are identified using the history of search and browsing behavior of many users over an extended time period, whose collective behavior provides a basis for computing source authority. We describe a user study which compared the suggestion of destinations with the previously proposed suggestion of related queries, as well as with traditional, unaided Web search. Results show that search enhanced by destination suggestions outperforms other systems for exploratory tasks, with best performance obtained from mining past user behavior at query-level granularity.
Nonlinear adaptive distance metric learning for clustering.
A good distance metric is crucial for many data mining tasks. To learn a metric in the unsupervised setting, most metric learning algorithms project observed data to a lowdimensional manifold, where geometric relationships such as pairwise distances are preserved. It can be extended to the nonlinear case by applying the kernel trick, which embeds the data into a feature space by specifying the kernel function that computes the dot products between data points in the feature space. In this paper, we propose a novel unsupervised Nonlinear Adaptive Metric Learning algorithm, called NAML, which performs clustering and distance metric learning simultaneously. NAML first maps the data to a high-dimensional space through a kernel function; then applies a linear projection to find a low-dimensional manifold where the separability of the data is maximized; and finally performs clustering in the low-dimensional space. The performance of NAML depends on the selection of the kernel function and the projection. We show that the joint kernel learning, dimensionality reduction, and clustering can be formulated as a trace maximization problem, which can be solved via an iterative procedure in the EM framework. Experimental results demonstrated the efficacy of the proposed algorithm.
Time%2Ddependent event hierarchy construction.

Semi%2Dsupervised Feature Selection via Spectral Analysis.

Traffic grooming in WDM SONET rings with multiple line speeds.

Physical Topology Design for All%2DOptical Networks.
Abstract — There are many advantages of deploying an alloptical network. Unfortunately, there are still few guidelines on how to properly design the physical topology for such a network. We propose an efficient physical topology design algorithm and we use the asymptotic growth rate of the provisioned capacity as a metric to compare various design alternatives. A higher asymptotic growth rate translates directly into higher deployment cost for large networks. Our study shows that taking fiber length into consideration can lead to lower capacity requirement. We also find that a sufficiently large fiber-to-node ratio is necessary in order to minimize the asymptotic growth in the provisioned capacity, increase capacity utilization and minimize the need for wavelength conversion. We study a real network and find that its fiber-to-node ratio is too low. As a result, large provisioned capacity is required and less than 55 % of the capacity is usable. By increasing the ratio, we can reduce the provisioned capacity and achieve close to 80 % utilization. I.
Query Selection Techniques for Efficient Crawling of Structured Web Sources.

Feature subset selection bias for classification learning.
Feature selection is often applied to highdimensional data prior to classification learning. Using the same training dataset in both selection and learning can result in socalled feature subset selection bias. This bias putatively can exacerbate data overfitting and negatively affect classification performance. However, in current practice separate datasets are seldom employed for selection and learning, because dividing the training data into two datasets for feature selection and classifier learning respectively reduces the amount of data that can be used in either task. This work attempts to address this dilemma. We formalize selection bias for classification learning, analyze its statistical properties, and study factors that affect selection bias, as well as how the bias impacts classification learning via various experiments. This research endeavors to provide illustration and explanation why the bias may not cause negative impact in classification as much as expected in regression. 1.
A Balanced Ensemble Approach to Weighting Classifiers for Text Classification.

Feature subset selection bias for classification learning.
Feature selection is often applied to highdimensional data prior to classification learning. Using the same training dataset in both selection and learning can result in socalled feature subset selection bias. This bias putatively can exacerbate data overfitting and negatively affect classification performance. However, in current practice separate datasets are seldom employed for selection and learning, because dividing the training data into two datasets for feature selection and classifier learning respectively reduces the amount of data that can be used in either task. This work attempts to address this dilemma. We formalize selection bias for classification learning, analyze its statistical properties, and study factors that affect selection bias, as well as how the bias impacts classification learning via various experiments. This research endeavors to provide illustration and explanation why the bias may not cause negative impact in classification as much as expected in regression. 1.
Power%2DLaw Tradeoffs Between Optical and Electronic Switching.

Some current issues of streaming data mining.

Discovering mappings in hierarchical data from multiple sources using the inherent structure.

Blocking objectionable web content by leveraging multiple information sources.
The World Wide Web has now become a humongous archive of various contents. The inordinate amount of information found on the web presents a challenge to deliver right information to the right users. On one hand, the abundant information is freely accessible to all web denizens; on the other hand, much of such information may be irrelevant or even deleterious to some users. For example, some control and filtering mechanisms are desired to prevent inappropriate or offensive materials such as pornographic websites from reaching children. Ways of accessing websites are termed as Access Scenarios. An Access Scenario can include using search engines (e.g., image search that has very little textual content), URL redirection to some websites, or directly typing (porn) website URLs. In this paper we propose a framework to analyze a website from several different aspects or information sources, and generate a classification model aiming to accurately classify such content irrespective of access scenarios. Extensive experiments are performed to evaluate the resulting system, which illustrates the promise of the proposed approach. 1.
Advances in Knowledge Discovery and Data Mining

BioLog A Browser Based Collaboration and Resource Navigation Assistant for BioMedical Researchers.
Abstract. We often realize that communicating with other colleagues who are studying similar topics helps to identify information relevant to our area of study, which otherwise may not have been found. We wish to accelerate acquisition of collective knowledge in a defined area by identifying specific spheres of inquiry. Such spheres correspond to groups of people who are experts in a field. In this paper we provide a systematic way to gain knowledge from their online search activity, and enable them to organize and share their search findings for further analysis. We have built a prototype system, BioLog, to help biomedical researchers share this implicit knowledge among their peers and store their access patterns into a central system for reuse. BioLog has been deployed it in two labs within TGen as a pilot study. The data has been gathered and analyzed by preliminary text-mining and collaborative filtering methods. 1
Error%2DSensitive Grading for Model Combination.

Sensor Sequence Modeling for Driving.

Bias Analysis in Text Classification for Highly Skewed Data.

Learning with Labeled Sessions.

A Novel Approach to Model Generation for Heterogeneous Data Classification.
Ensemble methods such as bagging and boosting have been successfully applied to classification problems. Two important issues associated with an ensemble approach are: how to generate models to construct an ensemble, and how to combine them for classification. In this paper, we focus on the problem of model generation for heterogeneous data classification. If we could partition heterogeneous data into a number of homogeneous partitions, we will likely generate reliable and accurate classification models over the homogeneous partitions. We examine different ways of forming homogeneous subsets and propose a novel method that allows a data point to be assigned multiple times in order to generate homogeneous partitions for ensemble learning. We present the details of the new algorithm and empirical studies over the UCI benchmark datasets and datasets of image classification, and show that the proposed approach is effective for heterogeneous data classification. 1
Traffic grooming in WDM SONET UPSR rings with multiple line speeds.

Research Paper Recommender Systems A Subspace Clustering Approach.
Researchers from the same lab often spend a considerable amount of time searching for published articles relevant to their current project. Despite having similar interests, they conduct independent, time consuming searches. While they may share the results afterwards, they are unable to leverage previous search results during the search process. We propose a research paper recommender system that avoids such time consuming searches by augmenting existing search engines with recommendations based on previous searches performed by others in the lab. Most existing recommender systems were developed for commercial domains with millions of users. The research paper domain has relatively few users compared to the large number of online research papers. The two major challenges with this type of data are the large number of dimensions and the sparseness of the data. The novel contribution of the paper is a scalable subspace clustering algorithm (SCuBA 1)thattackles these problems. Both synthetic and benchmark datasets are used to evaluate the clustering algorithm and to demonstrate that it performs better than the traditional collaborative filtering approaches when recommending research papers. 

CubeSVD a novel approach to personalized Web search.
As the competition of Web search market increases, there is a high demand for personalized Web search to conduct retrieval incorporating Web users&#039; information needs. This paper focuses on utilizing clickthrough data to improve Web search. Since millions of searches are conducted everyday, a search engine accumulates a large volume of clickthrough data, which records who submits queries and which pages he/she clicks on. The clickthrough data is highly sparse and contains di#erent types of objects (user, query and Web page), and the relationships among these objects are also very complicated. By performing analysis on these data, we attempt to discover Web users&#039; interests and the patterns that users locate information. In this paper, a novel approach CubeSVD is proposed to improve Web search. The clickthrough data is represented by a 3-order tensor, on which we perform 3-mode analysis using the higher-order singular value decomposition technique to automatically capture  the latent factors that govern the relations among these multi-type objects: users, queries and Web pages. A tensor reconstructed based on the CubeSVD analysis reflects both the observed interactions among these objects and the implicit associations among them. Therefore, Web search activities can be carried out based on CubeSVD analysis. Experimental evaluations using a real-world data set collected from an MSN search engine show that CubeSVD achieves encouraging search results in comparison with some standard methods.
Evolving Feature Selection.
We describe an evolutionary approach to active vision systems for dynamic feature selection. After summarizing recent work on evolution of a simulated active retina for complex shape discrimination, we describe in detail experiments that extend this approach to an all-terrain mobile robot equipped with a mobile camera. We show that evolved robots are capable of selecting simple visual features and actively maintaining them on the same retinal position, which largely simplifies the “recognition ” task, in order to generate efficient navigation trajectories with an extremely simple neural control system. Analysis of evolved solutions indicates that robots develop a simple
Toward Integrating Feature Selection Algorithms for Classification and Clustering.
This paper introduces concepts and algorithms of feature selection, surveys existing feature selection algorithms for classification and clustering, groups and compares different algorithms with a categorizing framework based on search strategies, evaluation criteria, and data mining tasks, reveals unattempted combinations, and provides guidelines in selecting feature selection algorithms. With the categorizing framework, we continue our efforts toward building an integrated system for intelligent feature selection. A unifying platform is proposed as an intermediate step. An illustrative example is presented to show how existing feature selection algorithms can be integrated into a meta algorithm that can take advantage of individual algorithms. An added advantage of doing so is to help a user employ a suitable algorithm without knowing details of each algorithm. Some real-world applications are included to demonstrate the use of feature selection in data mining. We conclude this work by identifying trends and challenges of feature selection research and development.
SWITCH A Novel Approach to Ensemble Learning for Heterogeneous Data.


Redundancy based feature selection for microarray data.
In gene expression microarray data analysis, selecting a small number of discriminative genes from thousands of genes is an important problem for accurate classification of diseases or phenotypes. The problem becomes particularly challenging due to the large number of features (genes) and small sample size. Traditional gene selection methods often select the top-ranked genes according to their individual discriminative power without handling the high degree of redundancy among the genes. Latest research shows that removing redundant genes among selected ones can achieve a better representation of the characteristics of the targeted phenotypes and lead to improved classification accuracy. Hence, we study in this paper the relationship between feature relevance and redundancy and propose an efficient method that can effectively remove redundant genes. The efficiency and effectiveness of our method in comparison with representative methods has been demonstrated through an empirical study using public microarray data sets.
Compact Dual Ensembles for Active Learning.

Class%2DSpecific Ensembles for Active Learning.
In many real-world tasks of image classification, limited amounts of labeled data are available to train automatic classifiers. Consequently, extensive human expert involvement is required for instance labeling. Detecting Egeria densa in digital imagery is one such real-world classification task. It presents an additional challenge due to subtle spectral changes in Egeria, which makes it difficult to find a single accurate classifier. A novel solution is proposed to employ an ensemble of classifiers for each class (class-specific ensembles), combined with an active learning scheme. The class-specific ensembles are implicitly diverse. Diversity is required to increase the overall accuracy when combining predictions. The combined predictions of the ensembles can be used to reduce the uncertainty in detecting Egeria. Iterative active learning is then suggested to adapt the ensembles to the new images, unseen to the active learner. A novel solution to build compact ensembles is also presented, which are needed to expedite the re-training of the active learner. The combined results are accurate and compact ensembles, which require significantly less expert involvement for image region classification. 1
An Empirical Study of Building Compact Ensembles.
Abstract. Ensemble methods can achieve excellent performance relying on member classifiers ’ accuracy and diversity. We conduct an empirical study of the relationship of ensemble sizes with ensemble accuracy and diversity, respectively. Experiments with benchmark data sets show that it is feasible to keep a small ensemble while maintaining accuracy and diversity similar to those of a full ensemble. We propose a heuristic method that can effectively select member classifiers to form a compact ensemble. The idea of compact ensembles is motivated to use them for effective active learning in tasks of classification of unlabeled data.
A selective sampling approach to active feature selection.
Feature selection, as a preprocessing step to machine learning, has been very effective in reducing dimensionality, removing irrelevant data, increasing learning accuracy, and improving result comprehensibility. Traditional feature selection methods resort to random sampling in dealing with data sets with a huge number of instances. In this paper, we introduce the concept of active feature selection, and investigate a selective sampling approach to active feature selection in a filter model setting. We present a formalism of selective sampling based on data variance, and apply it to a widely used feature selection algorithm Relief. Further, we show how it realizes active feature selection and reduces the required number of training instances to achieve time savings without performance deterioration. We design objective evaluation measures of performance, conduct extensive experiments using both synthetic and benchmark data sets, and observe consistent and significant improvement. We suggest some further work based on our study and experiments.
Efficient Feature Selection via Analysis of Relevance and Redundancy.
Feature selection is applied to reduce the number of features in many applications where data has hundreds or thousands of features. Existing feature selection methods mainly focus on finding relevant features. In this paper, we show that feature relevance alone is insufficient for efficient feature selection of high-dimensional data. We define feature redundancy and propose to perform explicit redundancy analysis in feature selection. A new framework is introduced that decouples relevance analysis and redundancy analysis. We develop a correlation-based method for relevance and redundancy analysis, and conduct an empirical study of its efficiency and effectiveness comparing with representative methods.
Active learning for detecting a spectrally variable subject in color infrared imagery.

Subspace clustering for high dimensional data a review.

Mining %22Hidden Phrase%22 Definitions from the Web.
Keyword searching is the most common form of document search on the Web. Many Web publishers manually annotate the META tags and titles of their pages with frequently queried phrases in order to improve their placement and ranking. A &#034;hidden phrase&#034; is defined as a phrase that occurs in the META tag of a Web page but not in its body. In this paper we present an algorithm that mines the definitions of hidden phrases from the Web documents. Phrase definitions allow (i) publishers to find relevant phrases with high query frequency, and, (ii) search engines to test if the content of the body of a document matches the phrases. We use cooccurrence clustering and association rule mining algorithms to learn phrase definitions from high-dimensional data sets. We also provide experimental results.
Situation%2DAware Personalized Information Retrieval for Mobile Internet.

Feature Selection for High%2DDimensional Data A Fast Correlation%2DBased Filter Solution.
Feature selection, as a preprocessing step to machine learning, is effective in reducing dimensionality, removing irrelevant data, increasing learning accuracy, and improving result comprehensibility. However, the recent increase of dimensionality of data poses a severe challenge to many existing feature selection methods with respect to efficiency and effectiveness. In this work, we introduce a novel concept, predominant correlation, and propose a fast filter method which can identify relevant features as well as redundancy among relevant features without pairwise correlation analysis. The efficiency and effectiveness of our method is demonstrated through extensive comparisons with other methods using real-world data of high dimensionality. 1.
Active Learning with Ensembles for Image Classification.
In many real-world tasks of image classification,  limited amounts of labeled data are available to  train automatic classifiers. Consequently, extensive  human expert involvement is required for verification.
Efficiently handling feature redundancy in high%2Ddimensional data.
High-dimensional data poses a severe challenge for data mining. Feature selection is a frequently used technique in preprocessing high-dimensional data for successful data mining. Traditionally, feature selection is focused on removing irrelevant features. However, for high-dimensional data, removing redundant features is equally critical. In this paper, we provide a study of feature redundancy in high-dimensional data and propose a novel correlation-based approach to feature selection within the filter model. The extensive empirical study using real-world data shows that the proposed approach is efficient and effective in removing redundant and irrelevant features.
Active Feature Selection Using Classes.
Abstract. Feature selection is frequently used in data pre-processing for data mining. When the training data set is too large, sampling is commonly used to overcome the difficulty. This work investigates the applicability of active sampling in feature selection in a filter model setting. Our objective is to partition data by taking advantage of class information so as to achieve the same or better performance for feature selection with fewer but more relevant instances than random sampling. Two versions of active feature selection that employ class information are proposed and empirically evaluated. In comparison with random sampling, we conduct extensive experiments with benchmark data sets, and analyze reasons why class-based active feature selection works in the way it does. The results will help us deal with large data sets and provide ideas to scale up other feature selection algorithms. 1
Consistency%2Dbased search in feature selection.

Fast hierarchical clustering and its validation.
Clustering is the task of grouping similar objects into clusters. A prominent and useful class of algorithm is hierarchical agglomerative clustering (HAC) which iteratively agglomerates the closest pair until all data points belong to one cluster. It outputs a dendrogram showing all N levels of agglomerations where N is the number of objects in the dataset. However, HAC methods have several drawbacks: (1) high time and memory complexities for clustering, and (2) inefficient and inaccurate cluster validation. In this paper we show that these drawbacks can be alleviated by closely studying the dendrogram. Empirical study shows that most HAC algorithms follow a trend where, except for a number of top levels of the dendrogram, all lower levels agglomerate clusters which are very small in size and close in proximity to other clusters. Methods are proposed that exploit this characteristic to reduce the time and memory complexities significantly and to make validation very efficient and accurate. Analysis and experiments show the effectiveness of the proposed method.
Efficient Mapping of Range Classifier into Ternary%2DCAM.
Packet classification is inherently a multi dimensional search problem which is either very computation intensive or memory intensive for software implementation. Thus, hardware based solution is necessary to keep up with gigabit line rate processing. In this paper, we consider using standard Ternary Content Addressable Memory (TCAM) as a hardware classification engine. Traditionally, this approach has been deemed inefficient because ranges have to be broken into prefixes before stored in TCAM, resulting in large expansion. We propose a novel scheme where we can efficiently map ranges into TCAM. Our proposal has no expansion at all, or very little expansion for width constrained application. Our proposal enables high speed deterministic classification using low cost commodity hardware.
Feature Selection for Clustering %2D A Filter Solution.
Processing applications with a large number of dimensions has been a challenge to the KDD community. Feature selection, an effective dimensionality reduction technique, is an essential pre-processing method to remove noisy features. In the literature there are only a few methods proposed for feature selection for clustering. And, almost all of those methods are `wrapper&#039; techniques that require a clustering algorithm to evaluate the candidate feature subsets. The wrapper approach is largely unsuitable in real-world applications due to its heavy reliance on clustering algorithms that require parameters such as number of clusters, and due to lack of suitable clustering criteria to evaluate clustering in different subspaces. In this paper we propose a `filter&#039; method that is independent of any clustering algorithm. The proposed method is based on the observation that data with clusters has very different point-to-point distance histogram than that of data without clusters. Using this we propose an entropy measure that is low if data has distinct clusters and high otherwise. The entropy measure is suitable for selecting the most important subset of features because it is invariant with number of dimensions, and is affected only by the quality of clustering. Extensive performance evaluation over synthetic, benchmark, and real datasets shows its effectiveness.
Feature Selection with Selective Sampling.
Feature selection, as a preprocessing step to  machine learning, has been shown very effective  in reducing dimensionality, removing  irrelevant data, increasing learning accuracy,  and improving comprehensibility. In this paper,  we consider the problem of active feature  selection in a  lter model setting. We  describe a formalism of active feature selection  called selective sampling, demonstrate it  by applying it to a widely used feature selection  algorithm Relief, and show how it realizes  active feature selection and reduces the  required number of training data for Relief  to achieve time savings without performance  deterioration. We design objective evaluation  measures, conduct extensive experiments using  bench-mark data sets, and observe consistent  and signi  cant improvement.
Feature Extraction for Image Mining.

On Issues of Instance Selection.
The digital technologies and computer advances with the booming internet uses have led to massive data collection (corporate data, data warehouses, webs, just to name a few) and information (or misinformation) explosion. Szalay and Gray described this phenomenon as “drowning in data” (Szalay and Gray, 1999). They reported that each year the detectors at the CERN particle collider in Switzerland record 1 petabyte of data; and researchers in areas of science from astronomy to the human genome are facing the same problems and choking on information. A very natural question is “now that we have gathered so much data, what do we do with it?” Raw data is rarely of direct use and manual analysis simply cannot keep pace with the fast growth of data. Data mining and knowledge discovery (KDD), as a new emerging field comprising disciplines such as databases, statistics, machine learning, comes to the rescue. KDD attempts to turn raw data into nuggets and create special edges in this ever competitive world for science discovery and business intelligence. The KDD process is defined in Fayyad et al. (1996) as the nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data. Data Mining processes include data selection, preprocessing, data mining, interpretation and evaluation.
Discretization An Enabling Technique.

Routing Table Compaction in Ternary CAM.

Sampling from databases using B%5E %2DTrees.

User Intention Modelling in Web Applications Using Data Mining.
The problem of inferring a user&#039;s intentions in Machine--Human Interaction has been the key research issue for providing personalized experiences and services. In this paper, we propose novel approaches on modeling and inferring user&#039;s actions in a computer. Two linguistic features -- keyword and concept features -- are extracted from the semantic context for intention modeling. Concept features are the conceptual generalization of keywords. Association rule mining is used to find the proper concept of corresponding keyword. A modified Nave Bayes classifier is used in our intention modeling. Experimental results have shown that our proposed approach achieved 84% average accuracy in predicting user&#039;s intention, which is close to the precision (92%) of human prediction.
%271   1 g%3B 2%27%3A Merging Distance and Density Based Clustering.

Efficiently Determine the Starting Sample Size for Progressive Sampling.
Given a large data set and a classification learning algorithm, Progressive Sampling (PS) uses increasingly larger random samples to learn until model accuracy no longer improves. It is shown that the technique is remarkably efficient compared to using the entire data. However, how to set the starting sample size for PS is still an open problem. We show that an improper starting sample size can still make PS expensive in computation due to running the learning algorithm on a large number of instances (of a sequence of random samples before achieving convergence) and excessive database scans to fetch the sample data. Using a suitable starting sample size can further improve the efficiency of PS. In this paper, we present a statistical approach which is able to efficiently find such a size. We call it the Statistical Optimal Sample Size (SOSS), in the sense that a sample of this size sufficiently resembles the entire data. We introduce an information-based measure of this resemblance (Sample Quality) to define the SOSS and show that it can be efficiently obtained in one scan of the data. We prove that learning on a sample of SOSS will produce model accuracy that asymptotically approaches the highest achievable accuracy on the entire data. Empirical results on a number of large data sets from the UCIKDD repository show that SOSS is a suitable starting size for Progressive Sampling.
Efficiently Determining the Starting Sample Size for Progressive Sampling.
Given a large data set and a classification learning algorithm, Progressive Sampling (PS) uses increasingly larger random samples to learn until model accuracy no longer improves. It is shown that the technique is remarkably efficient compared to using the entire data. However, how to set the starting sample size for PS is still an open problem. We show that an improper starting sample size can still make PS expensive in computation due to running the learning algorithm on a large number of instances (of a sequence of random samples before achieving convergence) and excessive database scans to fetch the sample data. Using a suitable starting sample size can further improve the efficiency of PS. In this paper, we present a statistical approach which is able to efficiently find such a size. We call it the Statistical Optimal Sample Size (SOSS), in the sense that a sample of this size sufficiently resembles the entire data. We introduce an information-based measure of this resemblance (Sample Quality) to define the SOSS and show that it can be efficiently obtained in one scan of the data. We prove that learning on a sample of SOSS will produce model accuracy that asymptotically approaches the highest achievable accuracy on the entire data. Empirical results on a number of large data sets from the UCIKDD repository show that SOSS is a suitable starting size for Progressive Sampling.
Efficient Yet Accurate Clustering.
To efficiently and yet accurately cluster web documents is of great interests to web users and is a key component of the searching accuracy of a web search engine. To achieve this, this paper introduces a new approach for the clustering of web documents, which is called Maximal Frequent Itemset(MFI) approach. Iterative clustering algorithms, such as K-means and Expectation-Maximization(EM), are sensitive to their initial conditions. MFI approach firstly locates the center points of high density clusters precisely. These center points then are used as initial points for the K-means algorithm. Our experimental results tested on 3 web document sets show that our MFI approach outperforms the other methods we compared in most cases, particularly in the case of large number of categories in web document sets. 1.
Efficient Hierarchical Clustering Algorithms Using Partially Overlapping Partitions.
. Clustering is an important data exploration task. A prominent  clustering algorithm is agglomerative hierarchical clustering. Roughly,  in each iteration, it merges the closest pair of clusters. It was first proposed  way back in 1951, and since then there have been numerous modifications.  Some of its good features are: a natural, simple, and nonparametric  grouping of similar objects which is capable of finding clusters  of different shape such as spherical and arbitrary. But large CPU  time and high memory requirement limit its use for large data. In this  paper we show that geometric metric (centroid, median, and minimum  variance) algorithms obey a 90-10 relationship where roughly the first  90iterations are spent on merging clusters with distance less than 10the  maximum merging distance. This characteristic is exploited by partially  overlapping partitioning. It is shown with experiments and analyses that  different types of existing algorithms benefit excellently by drastical...
Modelling Classification Performance for Large Data Sets.
. For many learning algorithms, their learning accuracy will  increase as the size of training data increases, forming the well-known  learning curve. Usually a learning curve can be fitted by interpolating  or extrapolating some points on it with a specified model. The obtained  learning curve can then be used to predict the maximum achievable  learning accuracy or to estimate the amount of data needed to achieve  an expected learning accuracy, both of which will be especially meaningful  to data mining on large data sets. Although some models have  been proposed to model learning curves, most of them do not test their  applicability to large data sets. In this paper, we focus on this issue.  We empirically compare six potentially useful models by fitting learning  curves of two typical classification algorithms---C4.5 (decision tree)  and LOG (logistic discrimination) on eight large UCI benchmark data  sets. By using all available data for learning, we fit a full-length learning  curve; by using a small portion of the data, we fit a part-length learning  curve. The models are then compared in terms of two performances: (1)  how well they fit a full-length learning curve, and (2) how well a fitted   part-length learning curve can predict learning accuracy at the full  length. Experimental results show that the power law (y = a  -  b  #  x -c )  is the best among the six models in both the performances for the two  algorithms and all the data sets. These results support the applicability  of learning curves to data mining.  1 
Toward Multidatabase Mining Identifying Relevant Databases.
Various tools and systems for knowledge discovery and data mining are developed and available for applications.
Rule mining with prior knowledge %2D a belief networks approach.
Some existing data mining methods, such as classification trees, neural networks and association rules, have the drawbacks that the user&#039;s prior knowledge cannot be easily specified and incorporated into the knowledge discovery process, and the rules mined from databases lack quantitative analyses. In this paper, we propose a belief networks method for rule mining, which takes the advantage of belief networks as the directed acyclic graph language and their function for numerical representation of probabilistic dependencies among the variables in the database, so that it can overcome the drawbacks. Since belief networks provide a natural representation for capturing causal relationship among a set of variables, our proposed method can mine more general correlation rules which can capture the relationship of more than two attribute variables. The potential application of the proposed method is 1  demonstrated through the detailed case studies on benchmark databases.  Keywords: Belief ne...
Resource Description Framework Metadata and Its Applications.

Knowledge Discovery and Data Mining

Rule Mining via Learning Belief Networks.

Sampling from Databases Using B %2DTrees.

Feature Selection for Clustering.
. Clustering is an important data mining task. Data mining  often concerns large and high-dimensional data but unfortunately most  of the clustering algorithms in the literature are sensitive to largeness or  high-dimensionality or both. Different features affect clusters differently,  some are important for clusters while others may hinder the clustering  task. An efficient way of handling it is by selecting a subset of important  features. It helps in finding clusters efficiently, understanding the data  better and reducing data size for efficient storage, collection and processing.  The task of finding original important features for unsupervised data  is largely untouched. Traditional feature selection algorithms work only  for supervised data where class information is available. For unsupervised  data, without class information, often principal components (PCs)  are used, but PCs still require all features and they may be difficult to  understand. Our approach: first features are...
Exception Rule Mining with a Relative Interestingness Measure.
. This paper presents a method for mining exception rules  based on a novel measure which estimates interestingness relative to its  corresponding common sense rule and reference rule. Mining interesting  rules is one of the important data mining tasks. Interesting rules bring  novel knowledge that helps decision makers for advantageous actions. It is  true that interestingness is a relative issue that depends on the other prior  knowledge. However, this estimation can be biased due to the incomplete  or inaccurate knowledge about the domain. Even if possible to estimate  interestingness, it is not so trivial to judge the interestingness from a  huge set of mined rules. Therefore, an automated system is required  that can exploit the knowledge extractacted from the data in measuring  interestingness. Since the extracted knowledge comes from the data, so  it is possible to find a measure that is unbiased from the user&#039;s own  belief. An unbiased measure that can estimate the interestingn...
Consistency Based Feature Selection.
. Feature selection is an effective technique in dealing with  dimensionality reduction for classification task, a main component of  data mining. It searches for an &#034;optimal&#034; subset of features. The search  strategies under consideration are one of the three: complete, heuristic,  and probabilistic. Existing algorithms adopt various measures to evaluate  the goodness of feature subsets. This work focuses on one measure called  consistency. We study its properties in comparison with other major  measures and different ways of using this measure in search of feature  subsets. We conduct an empirical study to examine the pros and cons of  these different search methods using consistency. Through this extensive  exercise, we aim to provide a comprehensive view of this measure and its  relations with other measures and a guideline of the use of this measure  with different search strategies facing a new application.  1 Introduction  Classification is an important data mining task. The basi...
Customer Retention via Data Mining.
. &#034;Customer Retention&#034; is an increasingly pressing issue in today&#039;s evercompetitive commercial arena. This is especially relevant and important for sales and services related industries. Motivated by a real-world problem faced by a large company, we proposed a solution that integrates the various techniques of data mining, such as feature selection via induction, deviation analysis, and mining multiple concept-level association rules to form an intuitive and novel approach to gauging customer loyalty and predicting their likelihood of defection. Immediate action triggered by these &#034;early-warnings&#034; resulted from data mining is often the key to eventual customer retention.  Keywords: Customer retention, feature selection, deviation analysis, multiple level association rules, data mining  1. Introduction  In the last decade, the increased dependency and widespread use of databases in almost every business, scientific and government organization has led to an explosive growth of data. Inst...
Handling Large Unsupervised Data via Dimensionality Reduction.


Mining Weak Rules.

Feature Selection Using Consistency Measure.

A Study of Support Vectors on Model Independent Example Selection.
As databases for real-world problems increase in size, there is a need in many situations to select and keep relevant training data for ecient storage and processing reasons. Support vector machines (SVMs) reportedly exhibit certain desirable properties in selecting and preserving useful training data as support vectors. This paper attempts to quantify the extent to which SVM training behaves like a model independent example selection procedure. Using several common machine-learning training databases, we compare the prediction results obtained by dierent classiers, trained with data selected by SVMs and by two other example selection methods (IB2 and random sampling). Some interesting observations are made with explanations.  1 Introduction  Example-based learning is an attractive framework for extracting knowledge from empirical data, with the goal of generalizing well on new input patterns. Many realworld processes can be formulated as a 2-way classi- cation task that may be solv...
Handling Concept Drifts in Incremental Learning with Support Vector Machines.
With the increase in the size of real-world databases, there is an ever-increasing need to scale up inductive learning algorithms. Incremental learning techniques are one possible solution to the scalability problem. In this paper, we propose three criteria to evaluate the robustness and reliability of incremental learning methods, and use them to study the robustness of an incremental training method for Support Vector Machines. We provide empirical results using benchmark machine learning datasets to show that support vectors form a succinct and sucient set for block-by-block incremental learning.  1 Introduction  When developing classiers using learning methods, more training data can reduce risk, but the learning process can get computationally intractable. This issue is becoming more evident with large amounts of data available [5]. Researchers in machine learning and data mining [2, 3, 7] have therefore been trying to scale up classical inductive learning algorithms to handle ex...
Efficient Search of Reliable Exceptions.
. Finding patterns from data sets is a fundamental task of data mining. If we categorize all patterns into strong, weak, and random,  conventional data mining techniques are designed only to find strong patterns, which hold for numerous objects and are usually consistent with the expectations of experts. While such strong patterns are helpful in prediction, the unexpectedness and contradiction exhibited by weak patterns are also very useful although they represent a relatively small number of objects. In this paper, we address the problem of finding weak patterns (i.e., reliable exceptions) from databases. A simple and efficient approach is proposed which uses deviation analysis to identify interesting exceptions and explore reliable ones. Besides, it is flexible in handling both subjective and objective exceptions. We demonstrate the effectiveness of the proposed approach through a set of real-life data sets, and present interesting findings. 1 Introduction  Data mining has attracted ...

Feature Transformation and Multivariate Decision Tree Induction.
. Univariate decision trees (UDT&#039;s) have inherent problems  of replication, repetition, and fragmentation. Multivariate decision trees  (MDT&#039;s) have been proposed to overcome some of the problems. Close  examination of the conventional ways of building MDT&#039;s, however, reveals  that the fragmentation problem still persists. A novel approach  is suggested to minimize the fragmentation problem by separating hyperplane  search from decision tree building. This is achieved by feature  transformation. Let the initial feature vector be x, the new feature vector  after feature transformation T is y, i.e., y = T (x). We can obtain  an MDT by (1) building a UDT on y; and (2) replacing new features y  at each node with the combinations of initial features x. We elaborate  on the advantages of this approach, the details of T , and why it is expected  to perform well. Experiments are conducted in order to confirm  the analysis, and results are compared to those of C4.5, OC1, and CART.  1 Introducti...
A Monotonic Measure for Optimal Feature Selection.
. Feature selection is a problem of choosing a subset of relevant  features. Researchers have been searching for optimal feature selection  methods. `Branch and Bound&#039; and Focus are two representatives. In general,  only exhaustive search can bring about the optimal subset. However,  under certain conditions, exhaustive search can be avoided without sacrificing  the subset&#039;s optimality. One such condition is that there exists a  monotonic measure with which `Branch and Bound&#039; can guarantee an optimal  subset. Unfortunately, most error- or distance-based measures are  not monotonic. A new measure is employed in this work that is monotonic  and fast to compute. With this measure, the search for relevant  features is guaranteed to be complete but not exhaustive. An empirical  study is conducted to show that the algorithm indeed lives up to what  it claims. Some discussion is given at the end.  1 Introduction  The basic problem of classification is to classify a given pattern (example) to ...
Identifying Relevant Databases for Multidatabase Mining.
. Various tools and systems for knowledge discovery and data mining are developed and available for applications. However, when we are immersed in heaps of databases, an immediate question facing practitioners is where we should start mining. In this paper, breaking away from the conventional data mining assumption that many databases be joined into one, we argue that the first step for multidatabase mining is to identify databases that are most likely relevant to an application; without doing so, the mining process can be lengthy, aimless and ineffective. A relevance measure is thus proposed to identify relevant databases for mining tasks with an objective to find patterns or regularities about certain attributes. An efficient implementation for identifying relevant databases is described. Experiments are conducted to validate the measure &#039;s performance and to show its promising applications. Keywords: multiple databases, data mining, query, relevance measure 1 Introduction  While res...
CFMD A Conflict%2DFree Multivariate Discretization Algorithm.

Hybrid Search of Feature Subsets.
. Feature selection is a search problem for an &#034;optimal&#034; subset  of features. The class separability is normally used as one of the basic  feature selection criteria. Instead of maximizing the class separability as  in the literature, this work adopts a criterion aiming to maintain the  discriminating power of the data. After examining the pros and cons of  two existing algorithms for feature selection, we propose a hybrid algorithm  of probabilistic and complete search that can take advantage of  both algorithms. It begins by running LVF (probabilistic search) to reduce  the number of features; then it runs &#034;Automatic Branch &amp; Bound  (ABB)&#034; (complete search). By imposing a limit on the amount of time  this algorithm can run, we obtain an approximation algorithm. The empirical  study suggests that dividing the time equally between the two  phases yields nearly the best performance, and that the hybrid search  algorithm substantially outperforms earlier methods in general.  1 Introducti...
A Data Mining Application Customes Retention at the Port of Singapore Authority %28PSA%29.

Incremental Feature Selection.
Feature selection is a problem of finding relevant features. When the  number of features of a dataset is large and its number of patterns is huge,  an effective method of feature selection can help in dimensionality reduction.  An incremental probabilistic algorithm is designed and implemented  as an alternative to the exhaustive and heuristic approaches. Theoretical  analysis is given to support the idea of the probabilistic algorithm in  finding an optimal or near-optimal subset of features. Experimental results  suggest that (1) the probabilistic algorithm is effective in obtaining  optimal/suboptimal feature subsets; (2) its incremental version expedites  feature selection further when the number of patterns is large and can  scale up without sacrificing the quality of selected features.  Keywords: Pattern Recognition, Machine Learning, Feature Selection,  Dimensionality Reduction  To appear in Applied Intelligence, Kluwer Academic Publishers.  0  1 Introduction  Feature selection...
Analysis of Hidden Representations by Greedy Clustering.

Guest Editors%27 Introduction Feature Transformation and Subset Selection.

NeuroLinear A System for Extracting Oblique Decision Rules from Neural Networks.
We present NeuroLinear, a system for extracting oblique decision rules from neural  networks that have been trained for classification of patterns. Each condition of an  oblique decision rule corresponds to a partition of the attribute space by a hyperplane  that is not necessarily axis-parallel. Allowing a set of such hyperplanes to form the  boundaries of the decision regions leads to a significant reduction in the number of  rules generated while maintaining the accuracy rates of the networks. We describe the  components of NeuroLinear in detail by way of two examples using artificial datasets.  Our experimental results on real-world datasets show that the system is effective in  extracting compact and comprehensible rules with high predictive accuracy from neural  networks.  Keywords: Rule extraction, oblique-rule, pruning, discretization.  1 Introduction  Neural networks have been widely applied to solve classification problems. Comparisons between neural networks and decision tre...
Feature Selection via Discretization.
Discretization can turn numeric attributes into discrete ones. Feature selection can eliminate some irrelevant and/or redundant attributes. Chi2 is a simple and general algorithm that uses the   2  statistic to discretize numeric attributes repeatedly until some inconsistencies are found in the data. It achieves feature selection via discretization. It can handle mixed attributes, work with multiclass  data, and remove irrelevant and redundant attributes.  Keywords--- discretization, feature selection, pattern classification I. Introduction  Feature selection can eliminate some irrelevant and/or redundant attributes. By using relevant features, classification algorithms can in general improve their predictive accuracy, shorten the learning period, and form simpler concepts. There are abundant feature selection algorithms. Some use methods like principle component to compose a smaller number of new features [11,12]; some select a subset of the original attributes [1,5]. This paper consi...
Feature Selection for Classification.
Feature selection has been the focus of interest for quite some time and much work has been done. With the creation of huge databases and the consequent requirements for good machine learning techniques, new problems arise and novel approaches to feature selection are in demand. This survey is a comprehensive overview of many existing methods from the 1970&#039;s to the present. It identifies four steps of a typical feature selection method, and categorizes the different existing methods in terms of generation procedures and evaluation functions, and reveals hitherto unattempted combinations of generation procedures and evaluation functions. Representative methods are chosen from each category for detailed explanation and discussion via example. Benchmark datasets with different characteristics are used for comparative study. The strengths and weaknesses of different methods are explained. Guidelines for applying feature selection methods are given based on data types and domain characteris...
NeuroLinear From neural networks to oblique decision rules.
We present NeuroLinear, a system for extracting oblique decision rules from neural  networks that have been trained for classification of patterns. Each condition of an  oblique decision rule corresponds to a partition of the attribute space by a hyperplane  that is not necessarily axis-parallel. Allowing a set of such hyperplanes to form the  boundaries of the decision regions leads to a significant reduction in the number of  rules generated while maintaining the accuracy rates of the networks. We describe the  components of NeuroLinear in detail by way of two examples using artificial datasets.  Our experimental results on real-world datasets show that the system is effective in  extracting compact and comprehensible rules with high predictive accuracy from neural  networks.  Keywords: Rule extraction, oblique-rule, pruning, discretization.  1 Introduction  Neural networks have been widely applied to solve classification problems. Comparisons between neural networks and decision tre...
A Probabilistic Approach to Feature Selection %2D A Filter Solution.
Feature selection can be defined as a problem  of finding a minimum set of M relevant attributes  that describes the dataset as well as  the original N attributes do, where M  N .  After examining the problems with both the  exhaustive and the heuristic approach to feature  selection, this paper proposes a probabilistic  approach. The theoretic analysis and  the experimental study show that the proposed  approach is simple to implement and  guaranteed to find the optimal if resources  permit. It is also fast in obtaining results  and effective in selecting features that improve  the performance of a learning algorithm.  An on-site application involving huge  datasets has been conducted independently.  It proves the effectiveness and scalability of  the proposed algorithm. Discussed also are  various aspects and applications of this feature  selection algorithm.  1 Introduction  The problem of feature selection can be defined as finding  M relevant attributes among the N original attrib...
Feature Selection and Classification %2D A Probabilistic Wrapper Approach.
Feature selection is defined as a problem to find a minimum set of M features for an inductive algorithm to achieve the highest predictive accuracy from the data described by the original N features where M  N . A probabilistic wrapper model is proposed as another method besides the exhaustive search and the heuristic approach. The aim of this model is to avoid local minima and exhaustive search. The highest predictive accuracy is the criterion in search of the smallest M . Analysis and experiments show that this model can effectively find relevant features and remove irrelevant ones in the context of improving the predictive accuracy of an induction algorithm. It is simple, straightforward, and providing fast solutions while searching for the optimal. The applications of such a model, its future work and some related issues are also discussed. 1. INTRODUCTION  The problem of feature selection can be defined as finding relevant M features among the original N  attributes, where M  N , ...
Improving Backpropagation Learning with Feature Selection.
There exist redundant, irrelevant and noisy data. Using proper data to train a network  can speed up training, simplify the learned structure, and improve its performance. A  two-phase training algorithm is proposed. In the first phase, the number of input units of  the network is determined by using an information base method. Only those attributes  that meet certain criteria for inclusion will be considered as the input to the network. In  the second phase, the number of hidden units of the network is selected automatically  based on the performance of the network on the training data. One hidden unit is added  at a time only if it is necessary. The experimental results show that this new algorithm  can achieve a faster learning time, a simpler network and an improved performance.  
Symbolic Representation of Neural Networks.
Although backpropagation neural networks generally predict better than decision trees  do for pattern classification problems, they are often regarded as black boxes, i.e., their  predictions cannot be explained as those of decision trees. In many applications, more  often than not, explicit knowledge is needed by human experts. This work derives symbolic  representations from a neural network to make epxlicit each prediction of the network. An  algorithm is proposed and implemented to extract symbolic rules from neural networks.
Effective Data Mining Using Neural Networks.
Classification is one of the data mining problems receiving great attention recently in the database community.  This paper presents an approach to discover symbolic classification rules using neural networks. Neural networks  have not been thought suited for data mining because how the classifications were made is not explicitly stated  as symbolic rules that are suitable for verification or interpretation by humans. With the proposed approach,  concise symbolic rules with high accuracy can be extracted from a neural network. The network is first trained  to achieve the required accuracy rate. Redundant connections of the network are then removed by a network  pruning algorithm. The activation values of the hidden units in the network are analyzed, and classification rules  are generated using the result of this analysis. The effectiveness of the proposed approach is clearly demonstrated  by the experimental results on a set of standard data mining test problems.  1 Introduction  One ...
Dimensionality reduction via discretization.
The existence of numeric data and large amounts of records in a database  pose a challenging task to explicit concepts extraction from the raw data. This  paper introduces a method that reduces data vertically and horizontally, keeps  the discriminating power of the original data, and paves the way for extracting  concepts. The method is based on discretization (vertical reduction) and feature  selection (horizontal reduction). The experimental results show that (1) the data  can be effectively reduced by the proposed method; (2) the predictive accuracy of  a classifier (C4.5) can be improved after data and dimensionality reduction; and  (3) the classification rules learned are simpler.  Key Word: Dimensionality Reduction, Discretization, Knowledge Discovery  0  1 Introduction  The wide use of computers brings forth proliferation of databases. Without the aid of computer, little of this flood of raw data will ever be seen and exploited by humans. Knowledge discovery systems in database...
Understanding Neural Networks via Rule Extraction.
Although backpropagation neural networks  generally predict better than decision trees do  for pattern classification problems, they are often  regarded as black boxes, i.e., their predictions  are not as interpretable as those of decision  trees. This paper argues that this is because  there has been no proper technique that  enables us to do so. With an algorithm that  can extract rules, by drawing parallels with  those of decision trees, we show that the predictions of a network can be explained via rules extracted  from it, thereby, the network can be understood. Experiments demonstrate that rules  extracted from neural networks are comparable  with those of decision trees in terms of predictive  accuracy, number of rules and average  number of conditions for a rule; they preserve  high predictive accuracy of original networks. 
Towards Effective Classfication Rule Extraction %28Abstract%29.

NeuroRule A Connectionist Approach to Data Mining.
Classification, which involves finding rules  that partition a given data set into disjoint  groups, is one class of data mining problems.  Approaches proposed so far for mining classification  rules for large databases are mainly decision  tree based symbolic learning methods.  The connectionist approach based on neural  networks has been thought not well suited  for data mining. One of the major reasons  cited is that knowledge generated by neural  networks is not explicitly represented in the  form of rules suitable for verification or interpretation  by humans. This paper examines  this issue. With our newly developed algorithms,  rules which are similar to, or more  concise than those generated by the symbolic  methods can be extracted from the neural networks.  The data mining process using neural  networks with the emphasis on rule extraction  is described. Experimental results and comparison  with previously published works are  presented. 
Critics for Knowledge%2DBased Design Systems.

